Матч 413, Бесконечная последовательность 2 (InfiniteSequence2)

Дивизион 1, Уровень 2

Рассмотрим бесконечную последовательность А, определенную следующим образом:

A₀ = 1,

A_i = A_{[i/p] – x} + A_{[i/q] – y} , i ³ 1

По заданным n, p, q, x, y вычислить A_n.

Класс: InfiniteSequence

Метод: long calc(long n, int p, int q)

Ограничения: 0 £ n £ 10¹³, 2 £ p, q £ 10⁹, 0 £ x, y £ 10⁹.

Вход. Целые значения n, p, q.

Выход. Значение A_n.

Пример входа

n	p	q	x	y
10000000	2	3	10000000	10000000
12	2	3	1	0
123	45	67	8	9

Пример выхода

2

8

2

РЕШЕНИЕ

рекурсия

Заведем массив m, для которого m[i] = A_i. Массив длины n £ 10¹³ не поместится в памяти, поэтому вычисленные значения A_i будем запоминать лишь для i < MAX = 5000000. Для нахождения A_i при i ³ MAX используем обычную рекурсию.

ПРОГРАММА

#include <stdio.h>

#define MAX 5000000

long long m[MAX];

class InfiniteSequence2

{

public:

long long calc(long long n, int p, int q, int x, int y)

{

long long temp;

if (n <= 0) return 1;

if ((n < MAX) && m[n]) return m[n];

temp = calc(n/p-x,p,q,x,y) + calc(n/q-y,p,q,x,y);

if (n < MAX) m[n] = temp;

return temp;

}

};